#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    //遍历(暴力求解)
    int ans1(vector<vector<string>>& matrix){
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return 0;
        }

        int core_size = 1;
        int row = matrix.size(), col = matrix[0].size();
        for(int i = 0; i < row-core_size+1; i++){
            for(int j = 0; j < col-core_size+1; j++){
                if(core_size > row-i){
                    break;
                }
                vector<vector<int>> submat(core_size, vector<int>(core_size, 0));
                for(int sub_i = i; sub_i != i+core_size; sub_i++){
                    for(int sub_j = j; sub_j != j+core_size; sub_j++){
                        if(matrix[sub_i][sub_j] == "1"){
                            submat[sub_i-i][sub_j-j] = 1;
                        }
                    }
                }
                int sum_val = sum(submat, core_size);
                if(sum_val == core_size * core_size){
                    core_size++;
                    j--;
                }
            }
        }
        return (core_size-1) * (core_size-1);
    }

    int sum(vector<vector<int>>& submat, int core_size){
        vector<vector<int>> core(core_size, vector<int>(core_size, 1));
        int ret = 0;
        int row = core.size(), col = core.size();
        for(int i = 0; i != row; i++){
            for(int j = 0; j != col; j++){
                ret = ret + core[i][j] * submat[i][j];
            }
        }
        return ret;
    }

    int ans2(vector<vector<string>>& matrix){
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return 0;
        }
        int ret = 0;
        int row = matrix.size(), col = matrix[0].size();
        vector<vector<int>> dp(row, vector<int>(col, 0));
        for(int i = 0; i != row; i++){
            for(int j = 0; j != col; j++){
                if(matrix[i][j] == "1"){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
                    }
                    ret = max(ret, dp[i][j]);
                }
            }
        }

        return ret * ret;
    }

};

void test1(){
    Solution s;
    vector<vector<string>> matrix = {
        {"1","0","1","0","0"},
        {"1","0","1","1","1"},
        {"1","1","1","1","1"},
        {"1","0","0","1","0"}
    };

    // int ret = s.ans1(matrix);
    int ret = s.ans2(matrix);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<vector<string>> matrix = {
        {"0","1"},
        {"1","0"}
    };

    int ret = s.ans1(matrix);
    cout << ret << endl;
}

void test3(){
    Solution s;
    vector<vector<string>> matrix = {
        {"0","0","0"},
        {"0","0","0"},
        {"1","1","1"}
    };

    int ret = s.ans1(matrix);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}